% Ejercicio "Gramática equivalente, símbolos directores y pila"
\subsection*{\fbox{\theejercicio} - Gram\'atica equivalente, s\'{\i}mbolos directores y pila}

\begin{enumerate}[1)]
\item Escribir la definici\'on formal de la funci\'on CABECERA.
\item Sea el lenguaje definido por la la gram\'atica:

\begin{center}
\begin{tabular}{|lcl|} \hline
        &               &                         \\
{\em E} & $\rightarrow$ & {\bf n} $=$ {\em E}     \\
{\em E} & $\rightarrow$ & {\em E} {\bf ,} {\em E} \\
{\em E} & $\rightarrow$ & {\bf n}                 \\
        &               &                         \\ \hline
\end{tabular}
\end{center}

Se sabe que ambos operadores son asociativos por la derecha y que el operador `,' tiene menor prioridad que el operador `$=$'. Hallar una gram\'atica equivalente que cumpla la condici\'on LL(1).
\item Hallar los conjuntos de s\'{\i}mbolos directores de la gram\'atica:

\begin{center}
\begin{tabular}{|lcl|} \hline
         &               &                  \\
{\em S'} & $\rightarrow$ & {\em S} {\bf \$} \\
{\em S}  & $\rightarrow$ & {\em AS}         \\
{\em S}  & $\rightarrow$ & {\em A}          \\
{\em A}  & $\rightarrow$ & {\bf a}{\em AB}  \\
{\em A}  & $\rightarrow$ & {\bf b}          \\
{\em B}  & $\rightarrow$ & {\bf c} {\em A}  \\
{\em B}  & $\rightarrow$ & $\varepsilon$    \\
         &               &                  \\ \hline
\end{tabular}
\end{center}

\item En el transcurso del an\'alisis sint\'actico LL(1) de una sentencia, la pila evoluciona seg\'un se muestra en la figura. Sabiendo que la gram\'atica ampliada tiene exactamente 6 reglas, determinar cu\'ales son estas reglas, cu\'al es la cadena analizada y si pertenece o no al lenguaje generado por la gram\'atica.

\begin{center}
\begin{tabular}{||c||c||c||c||c||c||c||c||c||c||c||}
         &          &          &          &          &          &          &          &          &          & \\ \cline{3-3}
         &          & {\bf b}  &          &          &          &          &          &          &          & \\ \cline{2-4} \cline{6-6}
         & {\em B}  & {\em B}  & {\em B}  &          & {\bf d}  &          &          &          &          & \\ \cline{2-8}
         & {\em C}  & {\em C}  & {\em C}  & {\em C}  & {\em A}  & {\em A}  & {\bf a}  &          &          & \\ \cline{1-9}
{\em S}  & {\bf a}  & {\bf a}  & {\bf a}  & {\bf a}  & {\bf a}  & {\bf a}  & {\bf a}  & {\bf a}  &          & \\ \cline{1-10}
{\bf \$} & {\bf \$} & {\bf \$} & {\bf \$} & {\bf \$} & {\bf \$} & {\bf \$} & {\bf \$} & {\bf \$} & {\bf \$} & \\ \hline \hline
\end{tabular}
\end{center}
\end{enumerate}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Apartado 1)

\medskip

Definici\'on de CABECERA:

Sea una gram\'atica de contexto libre $G(N,T,P,S)$

Sean $\alpha, \beta \in (N \cup T)^*$.

Se define la funci\'on $CABECERA(\alpha): (N \cup T)^* \longmapsto T \cup \{\varepsilon\}$ como:

\smallskip

$
CABECERA(\alpha) = \left\{
\begin{array}{lcl}
\{a \in T | \alpha \Rightarrow^* a\beta\} \cup \{\varepsilon\} & \mbox{si} & \alpha \Rightarrow^* \varepsilon \\
                                                               &           &                                  \\
\{a \in T | \alpha \Rightarrow^* a\beta\}                      &           & \mbox{en otro caso}
\end{array} \right.
$

\medskip

Apartado 2)

Gram\'atica LL(1) equivalente:

\begin{center}
\begin{tabular}{|lcl|} \hline
         &               &                   \\
{\em S}  & $\rightarrow$ & {\em E} {\bf \$}  \\
{\em E}  & $\rightarrow$ & {\em TE}          \\
{\em E'} & $\rightarrow$ & {\bf ,} {\em TE'} \\
         & $|$           & $\varepsilon$     \\
{\em T}  & $\rightarrow$ & {\bf n}{\em T'}   \\
{\em T'} & $\rightarrow$ & {\bf n}{\em T'}   \\
{\em T'} & $|$           & $\varepsilon$     \\
         &               &                   \\ \hline
\end{tabular}
\end{center}

Apartado 3)

\begin{center}
\begin{tabular}{|lcl|l|} \hline
         &               &                  & {\bf S\'{\i}mbolos directores} \\ \hline
{\em S}  & $\rightarrow$ & {\em AS}         & {\bf a b}                      \\
{\em S}  & $\rightarrow$ & {\em A}          & {\bf a b}                      \\
{\em A}  & $\rightarrow$ & {\bf a}{\em AB}  & {\bf a}                        \\
{\em A}  & $\rightarrow$ & {\bf b}          & {\bf b}                        \\
{\em B}  & $\rightarrow$ & {\bf c} {\em A}  & {\bf c}                        \\
{\em B}  & $\rightarrow$ & $\varepsilon$    & {\bf a b c \$}                 \\ \hline
\end{tabular}
\end{center}

Apartado 4)

Las reglas de la gram\'atica son las siguientes:

\begin{center}
\begin{tabular}{|lcl|} \hline
          &               &                 \\
{\em S'}  & $\rightarrow$ & {\em A}{\bf \$} \\
{\em A}   & $\rightarrow$ & {\em BC}{\bf a} \\
{\em B}   & $\rightarrow$ & {\bf b}{\em B}  \\
          & $|$           & $\varepsilon$   \\
{\em C}   & $\rightarrow$ & {\bf d} {\em A} \\
{\em A}   & $\rightarrow$ & $\varepsilon$   \\
          &               &                 \\ \hline
\end{tabular}
\end{center}

La cadena analizada se corresponde con:

\begin{center}
\fbox{{\bf bdaa\$}}
\end{center}

la cual {\bf S\'I} pertenece al lenguaje.